/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/total-hamming-distance
   @Language: C++
   @Datetime: 19-04-27 15:50
   */

class Solution {
public:
	/**
	 * @param nums: the gievn integers
	 * @return: the total Hamming distance between all pairs of the given numbers
	 */
	int totalHammingDistance(vector<int> &nums) {
		// Write your code here
		int count=0;
		for(int i=1; i<=pow(10,9); i<<=1){
			int one=0;
			for(const int &a:nums)
				one += i&a?1:0;
			if(one) count += one*(nums.size()-one);
		}
		return count;
	}
};
